It has been quite well-known that due to the complexity of integrated circuits, it is not possible to apply a finite set of test vectors to verify the circuit delays for all the critical paths in the chip. Therefore, the vector-less approach or Static Timing Analysis (STA) is used widely to verify the timing of chip for each corner case with fixed gate delays. However, in today's nanometer process technology the manufacturing process variation plays a significant role in circuit delays, making SSTA increasingly important. Furthermore, interconnect part can be as dominant as the gate part in today's technology. Therefore, the issue of including process variation effect in the study of interconnect becomes extremely important.
SSTA is formalized in a way very similar to that of STA in terms of path tracing algorithm, but with quite a few differences. In STA, the gate delay is a fixed number, while in SSTA the delay is expressed as a random variable with some probability distribution function (PDF). In STA the critical paths are presented to the users based on slack which is the delay exceeding the timing limit. However, SSTA uses slack which means the probability of the occurrence of the critical path exceeding the use-specified threshold in terms of probability. In the presence of multi-phase sequential elements the timing constraints become complicated in the sense that the timing constraint is not uniform for all the paths, thus complicating the path tracing algorithms based on the breadth first search approach. Some specific algorithm in STA has been described in detail by Chang before. For example in STA the latest arrival time with respect to clock phases are stored at each node, while in SSTA the node stored accumulated probability. The path tracing procedure in terms of probability used in this invention is different from algorithm used by Visweswariah.
The process of calculating the aforementioned accumulated probability in SSTA at each node can be much more involved than that of storing the latest arrival time in STA. In SSTA, first we need to store the latest arrival time by using the max operation for all arrival times from each input of the gate with all the arrival times being expressed by random variables. Even we start with Gaussian distribution after max operation the result becomes non-Gaussian. Therefore, we need to handle max operation for Non-Gaussian distribution. If a random variable, is the linear combination of several Gaussian variables, then this random variable is Gaussian. To include non-Gaussian behavior, this random variable needs to be expressed as a sum of each Gaussian random variables to the second order. Zhan has proposed an algorithm to handle max operation with non-Gaussian distributions. The concept of edge probability can be understood as follows. For gate C with two inputs A and B, we use the notation that A is the random variable of the latest arrival time at the output of gate C for signal propagating from A to the output of gate C, and random variable B is defined similarly. For gate C with two inputs A and B the edge probability from A to output of C is Prob(A>B) meaning the probability of the latest signal at gate output coming from A by taking the integral of the PDF of Prob(A>B). Prob(B>A) then follows from 1-Prob(A>B). The accumulated probability at the given node then is evaluated by taking the largest of the products of edge probability for each gate along the path reaching this said node. We have adopted the algorithm of carrying out breadth first search to achieve these aforementioned accumulated probability for each node and then using depth first traversal to trace backward recursively to generate the critical paths with probability of occurrence greater than a specified probability threshold.
In SSTA with non-Gaussian delay distribution, the procedure of pre-characterizing the timing library to quadratic order of the Gaussian random variables is quite different from that of STA. The timing library in STA stores the gate delay as a function of gate input slope and gate output loading. In SSTA, this timing library stores the coefficients which are random variables in terms of sum of several Gaussian random variables up to quadratic order, while in STA the said coefficients are merely numbers. In evaluating the non-Gaussian delay distribution function use slope and output load as random variables up to quadratic order for the Gaussian random variables, and the coefficients from the equation also to the second order.
The process of calculating the aforementioned accumulated probability in SSTA at each node can be further complicated in the presence of interconnect. In STA the effective capacitance is already quite well-known. In this approach the gate driving the interconnect part is decomposed into two stages, the first stage is the driving gate with the effective capacitance and the output of the immediate output of the driving gate serves as the driving point of the second stage, namely the interconnect. Therefore, driving point admittance matrix and voltage transfer from the driving point to interconnect outputs are needed to calculate the delay from the input of the gate to both the immediate output of the gate and the interconnect outputs. A mathematical algorithm is presented to calculate admittance matrix and voltage transfer to the second order in powers of those Gaussian random variables due to manufacturing process variation. Subsequently, all the poles and residues for both admittance matrix and voltage transfer are also expressed to the second order in powers of Gaussian random variables. Thus, voltage wave function also expressed as random variable is obtained and delay distribution can be obtained.
In the case of cross-talk, effective capacitance approach by using the admittance matrix with poles and residues with variations up to the second order is also adopted. The effective capacitance of each gate by taking into account of the shift time of aggressor's input with respect to the victim's input are calculated and using admittance matrix with poles and residues with variations up to the second order. As to the victim delays from the immediate output of the input driver to the victim outputs, they are calculated by making use voltage transfer up to the 2nd order variation effect. Again, in SSTA, all of these delay quantities are treated as non-Gaussian random variables.
Finally, with all delay information in place, path search is continued until all critical paths in terms of probability are identified.